package com.c2b.algorithm.leetcode.jzoffer;

/**
 * <a href = "https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/">和为S的两个数字</a>
 * <p>输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。</p>
 * 限制：
 * 1 <= nums.length <= 10^5 ;
 * 1 <= nums[i] <= 10^6
 *
 * @author c2b
 * @since 2023/3/8 15:19
 */
public class JzOffer0057FindNumbersWithSum_S {
    /**
     * 双指针
     */
    public int[] FindNumbersWithSum(int[] nums, int target) {
        //  双指针 i , j 分别指向数组nums 的左右两端。
        int left = 0;
        int right = nums.length - 1;
        // 当双指针相遇时跳出
        while (left < right) {
            int currentVal = nums[left] + nums[right];
            if (currentVal < target) {
                // s<target ，则指针 i 向右移动，即执行 i=i+1
                left++;
            } else if (currentVal > target) {
                // s>target ，则指针 j 向左移动，即执行 j=j−1
                right--;
            } else {
                // s=target ，立即返回数组 [nums[i],nums[j]]
                return new int[]{nums[left], nums[right]};
            }
        }
        return new int[0];
    }

    public static void main(String[] args) {
        JzOffer0057FindNumbersWithSum_S jzOffer0057FindNumbersWithSum = new JzOffer0057FindNumbersWithSum_S();
        for (int i : jzOffer0057FindNumbersWithSum.FindNumbersWithSum(new int[]{1, 2, 2, 4, 5}, 4)) {
            System.out.println(i);
        }

    }
}
